package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;

import java.util.*;

/**
 * 层序遍历二叉树
 */
public class BiTree03_LevelOrder {

    public static void main(String[] args) {

    }

    /**
     * 解法一：迭代，通过队列实现广度优先遍历（BFS），层次遍历二叉树
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        // 存储层次遍历结果的列表
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        // 用队列来存储每层的节点
        Queue<TreeNode> queue = new ArrayDeque<>();
        // 将根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 存储当前层的遍历结果
            List<Integer> levelList = new ArrayList<>();
            // 获取当前层的节点数量
            int size = queue.size();
            // 遍历当前层节点，再把下一层节点入队
            for (int i = 0; i < size; i++) {
                // 出队当前节点，放入当前层的列表中
                TreeNode node = queue.poll();
                levelList.add(node.val);
                // 如果当前节点的左子节点不为空，将其入队
                if (node.left != null) {
                    queue.add(node.left);
                }
                // 如果当前节点的右子节点不为空，将其入队
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            // 保存当前层节点遍历结果
            resultList.add(levelList);
        }
        // 返回层次遍历的结果
        return resultList;
    }

    /**
     * 解法二：递归，通过深度优先遍历（DFS）的方式进行层序遍历，在遍历二叉树的同时，按层次记录结果
     */
    public static List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList<>();
        dfs(root, 1, resultList);
        return resultList;
    }

    /**
     * 深度优先遍历 DFS
     * @param node 表示当前节点
     * @param deep 表示当前节点的深度，又能表示层序遍历的结果列表大小
     * @param resultList 层序遍历结果
     */
    public static void dfs(TreeNode node, int deep, List<List<Integer>> resultList) {
        if (node == null) {
            return;
        }

        // 创建 deep 层的列表，仅遍历每层第一个节点时才会创建
        // 确保每个层级都有对应的列表来存储该层的节点值
        if (resultList.size() < deep) {
            resultList.add(new ArrayList<>());
        }

        // 保存第 deep 层的遍历结果
        // 将当前节点的值添加到对应层级的列表中
        resultList.get(deep - 1).add(node.val);

        // 递归处理左右子树，即下一层节点
        dfs(node.left, deep + 1, resultList);
        dfs(node.right, deep + 1, resultList);
    }

}
